use std::borrow::Borrow;
use std::cmp::Ordering;
use std::collections::{BTreeMap, HashMap, HashSet};
use std::str::{Chars, FromStr};
use std::vec;

//  题目1，两数之和
pub fn two_sum(nums: &Vec<i32>, target: i32) -> Vec<i32> {
    let mut ht: HashMap<i32, usize> = HashMap::new();
    let mut i = 0;
    let mut v: Vec<i32> = Vec::new();

    while i < nums.len() {
        let j = target - nums[i];

        match ht.get(&j) {
            Some(index) => {
                v.push(*index as i32);
                v.push(i as i32);
                return v;
            }
            None => {
                ht.insert(nums[i], i);
            }
        }
        i += 1;
    }

    return v;
}

pub fn generate_parenthesis(n: i32) -> Vec<String> {
    let mut res: Vec<String> = Vec::new();

    if n == 0 {
        return res;
    }

    if n == 1 {
        res.push(String::from("()"));
        return res;
    }
    let cur = &mut String::from("");
    dfs(cur, n, n, &mut res);
    return res;
}

// cur是当前递归得到的括号，lc是剩余的左括号数，rc是剩余的右括号数,v是容器
pub fn dfs(cur: &mut String, lc: i32, rc: i32, v: &mut Vec<String>) {
    if lc == rc && lc == 0 {
        v.push(cur.clone());
        return;
    }

    // 剪枝
    if lc > rc {
        return;
    }

    if lc > 0 {
        cur.push('(');
        dfs(cur, lc - 1, rc, v);
        cur.pop();
    }

    if rc > 0 {
        cur.push(')');
        dfs(cur, lc, rc - 1, v);
        cur.pop();
    }
}

//题目9 ，回文数
pub fn is_palindrome(x: i32) -> bool {
    // 为负数直接返回false;
    if x < 0 || (x % 10 == 0 && x != 0) {
        return false;
    }

    //   --- 如果是回文数，则反转后一半的数字应该与前一半的数字相同---
    let mut x = x;
    let mut revert_num = 0;
    while x > revert_num {
        // 通过模10来获取x的最后一位数字 ,将每次获取的x的最后一位数字拼接到 revert_num的最后一位
        revert_num = revert_num * 10 + x % 10;
        x /= 10;
    }

    // 当x <= revert_num时，则说明反转过半了，
    // 如果x < revert_num，有2种可能：1是原数字x不是回文数组； 2是原数字x的长度是奇数位，所以需要去除revert_num的最后一位再进行比较
    return if x != revert_num && x != revert_num / 10 {
        false
    } else {
        true
    };
}

// 题目13， 罗马数字转整数
pub fn roman_to_int(s: String) -> i32 {
    // 结果值
    let mut sum = 0;
    // 上一个字符的值
    let mut last = 0;
    //  将String按照char分割,将所有罗马字符转换为数字
    for c in s.chars() {
        let v = get_remo_value(c);
        if last != 0 && last < v {
            // 前一个值小于当前的值，则说明需要减去2倍last
            sum -= 2 * last;
        }
        sum += v;
        last = v;
    }

    sum
}

// 14题，最长公共前缀
pub fn longest_common_prefix(strs: Vec<String>) -> String {
    let mut result = String::new();
    // 用数组中的第一个字符串的元素做标准，然后遍历其他字符串，知道结束或者不相等即可得到最长公共前缀
    for i in 0..strs[0].len() {
        let standard = strs[0].chars().nth(i);
        let pass = strs.iter().skip(1).all(|f| f.chars().nth(i) == standard);
        if pass {
            result.push(standard.unwrap());
        } else {
            break;
        }
    }
    result
}

//题目 20题，  有效的括号.栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
// https://leetcode-cn.com/problems/valid-parentheses/
pub fn is_valid(s: String) -> bool {
    let bs = s.into_bytes();
    if bs.len() == 0 {
        return false;
    }
    // 用vec模拟栈
    let mut v = Vec::with_capacity(bs.len());

    // 遍历字符串
    for c in bs.iter().copied() {
        match c {
            b'(' => v.push(b')'),
            b'[' => v.push(b']'),
            b'{' => v.push(b'}'),
            _ => {
                if v.pop() != Some(c) {
                    return false;
                }
            }
        }
    }

    v.shrink_to_fit();
    v.is_empty()
}

// 第3题 ， 无重复最长子串
pub fn length_of_longest_substring(s: String) -> i32 {
    // 采用hash表+滑动窗口处理，hash表存储窗口中元素的索引位置，用滑动窗口变量所有元素，如果滑动过程中新添加的元素不在hash表中，那么就put进hash
    // 如果存在，且索引位置index在窗口窗口内，那么窗口的左指针移动到index+1

    let mut hash: HashMap<char, i32> = HashMap::with_capacity(s.len());
    // 设置左指针初始值为-1
    let mut left = -1;
    let mut max = 0;
    // 用迭代器遍历所有元素,i就相当于窗口的右指针
    s.chars().enumerate().for_each(|(i, c)| {
        // 如果元素c已经存在，更新左指针left的位置为max(left,索引值);
        left = left.max(*hash.get(&c).unwrap_or(&(-1)));
        // 窗口滑动，将元素的索引添加或更新到hash表中
        hash.insert(c, i as i32);
        // 计算窗口最大值.
        max = max.max(i as i32 - left);
    });
    max as i32
}

// 题目：806 写字符串需要的行数
// 思路： 遍历所有元素，计算每一行使用的总单位数，如果加上某个字符的单位数会超过100，则行数+1
pub fn number_of_lines(widths: Vec<i32>, s: String) -> Vec<i32> {
    // 最后一行使用的单位数
    let mut total: i32 = 0;
    // s有内容才需要行数
    let mut line = match s.len() > 0 {
        true => 1,
        false => 0,
    };
    let mut tmp = 0;
    for c in s.chars() {
        tmp = widths[(c as u8 - 97) as usize];
        if tmp + total > 100 {
            total = tmp;
            line += 1;
        } else {
            total += tmp;
        }
    }

    vec![line, total]
}

// 题目：4
// 思路：普通思路必定需要合并2个有序数组，然后遍历所有元素找到中位数，但是不一定需要合并完所有元素。可以看成是不断对某一个有序数组中添加元素，只要当添加的元素所在位置>=中位数位置，也就找到了中位数
pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
    // 总元素长度
    let total_len = nums1.len() + nums2.len();

    // 总长度是否是奇数
    let odd_flg = match total_len % 2 == 0 {
        true => false,
        false => true,
    };
    // 中位数索引位置，
    let middle = total_len / 2;

    // 处理某一个数组为空
    if nums1.len() == 0 {
        return get_middle_val(&nums2, middle, odd_flg);
    } else if nums2.len() == 0 {
        return get_middle_val(&nums1, middle, odd_flg);
    }

    let mut nums1 = nums1;
    let mut nums2 = nums2;

    // 找到起始元素最小的数组，用来做被插入的数组
    let mut standard = &mut nums1;
    let mut arry = &nums2;

    if arry.get(0).unwrap() < standard.get(0).unwrap() {
        standard = &mut nums2;
        arry = &nums1;
    }

    let mut i = 0;
    for k in arry.iter() {
        while i <= middle {
            if (i >= standard.len()) {
                standard.insert(i, *k);
                i += 1;
                break;
            } else {
                let x = *standard.get(i).unwrap();
                if *k < x {
                    standard.insert(i, *k);
                    i += 1;
                    break;
                } else {
                    i += 1;
                }
            }
        }
    }
    return get_middle_val(&standard, middle, odd_flg);
}

// 题目6，Z字型变换
pub fn convert(s: String, num_rows: i32) -> String {
    // 行数为1，或者字符串长度<=行数的情况下，都可以用1行表示，那么原字符串没有变动，直接返回
    if num_rows == 1 || s.len() as i32 <= num_rows {
        return s;
    }

    // 通过观察可得出规律，转换成的Z型字符串是以行数长度为周期的，可得出以下规律：
    // 1. 列上的元素对应的下一个周期上的列元素与上一个元素相差 2*(n-1)个，n为总行数
    // 2. 第0行与第0-1行与下一个周期元素之间的没有同行元素, 其他行元素与其对应的下一个周期的元素之间有一个同行元素，且该元素的与的坐标为 (num_rows - 1 - i) * 2 + j , j为上一个元素的索引值，i为行数索引值

    let mut result = String::new();
    let bytes = s.as_bytes();
    for i in 0..num_rows {
        let mut j = i;
        let mut middle_flg = false;
        if i != 0 && i != num_rows - 1 {
            middle_flg = true;
        }

        while s.len() > j as usize {
            result.push(bytes[j as usize] as char);
            if middle_flg {
                let middle = (num_rows - 1 - i) * 2 + j;
                if middle as usize >= s.len() {
                    break;
                } else {
                    result.push(bytes[middle as usize] as char);
                }
            }
            j = (num_rows - 1) * 2 + j;
        }
    }

    result
}

// 获取中位数的值. v是要查询的数组，index是中位数的索引，ood_flg是长度是否是奇数的标识
pub fn get_middle_val(v: &Vec<i32>, index: usize, ood_flg: bool) -> f64 {
    if ood_flg {
        (*v.get(index).unwrap()) as f64
    } else {
        let tmp = *(v.get(index - 1).unwrap()) + *(v.get(index).unwrap());
        tmp as f64 / 2 as f64
    }
}

// 题目7，整数反转   https://leetcode-cn.com/problems/reverse-integer/
pub fn reverse(x: i32) -> i32 {
    let mut res = 0;
    let mut x = x;
    let max = i32::MAX / 10;
    let min = i32::MIN / 10;

    while x != 0 {
        if res > max || res < min {
            return 0;
        }
        res = res * 10 + x % 10;
        x /= 10;
    }
    res
}

// 题目8，字符串转整数 https://leetcode-cn.com/problems/string-to-integer-atoi/
pub fn my_atoi(s: String) -> i32 {
    let max = i32::MAX / 10;
    let max_v = 7;
    let min = i32::MIN / 10;
    let min_v = 8;
    let mut res: i32 = 0;
    let mut negative = false;
    for (index, v) in s.trim().chars().enumerate() {
        if index == 0 && v == '+' {
            continue;
        }
        if index == 0 && v == '-' {
            negative = true;
            continue;
        }
        if v.is_numeric() {
            let k = v.to_digit(10).unwrap() as i32;
            // 负数
            if negative {
                if res < min || res == min && k > min_v {
                    return i32::MIN;
                }
                res = res * 10 - k;
            } else {
                if res > max || res == max && k > max_v {
                    return i32::MAX;
                }
                res = res * 10 + k;
            }
        } else {
            break;
        }
    }

    res
}

// 状态机节点
pub struct state_machine_node {
    // 状态值
    state: usize,
    // 状态转移函数
    f: HashMap<Option<char>, usize>,
}

// 根据模式串p生成有穷状态自动机
pub fn create_NFA(p: String) -> HashMap<usize, state_machine_node> {
    // NFA 状态转换的映射表
    let mut machine: HashMap<usize, state_machine_node> = HashMap::new();

    let mut i = 0;
    let mut last_c = '0';
    for c in p.chars() {
        if !machine.contains_key(&i) {
            machine.insert(
                i,
                state_machine_node {
                    state: i,
                    f: HashMap::new(),
                },
            );
        }

        if c != '*' {
            let node = machine.get_mut(&i);
            // 字符c匹配到下一个状态
            node.unwrap().f.insert(Some(c), i + 1);
            last_c = c;
        } else {
            // ---------  字符为'*' -------
            let last = machine.get_mut(&(i - 1)).unwrap();

            // 匹配0个
            last.f.insert(None, i + 1);

            let node = machine.get_mut(&i);

            // 匹配一个
            node.unwrap().f.insert(Some(last_c), i + 1);

            // 匹配多个
            let next = match machine.get_mut(&(i + 1)) {
                Some(n) => n,
                None => {
                    let n = state_machine_node {
                        state: i + 1,
                        f: HashMap::new(),
                    };
                    machine.insert(n.state, n);
                    machine.get_mut(&(i + 1)).unwrap()
                }
            };

            next.f.insert(Some(last_c), next.state);
        }

        // 提前创建下一个状态，这样在遍历到模式串p最后一个字符时才能拥有接收态
        if !machine.contains_key(&(i + 1)) {
            let n = state_machine_node {
                state: i + 1,
                f: HashMap::new(),
            };
            machine.insert(n.state, n);
        }

        i += 1;
    }

    machine
}

// todo: 题目10，正则表达式匹配 https://leetcode-cn.com/problems/regular-expression-matching/
// todo: 未完成，NFA与DFA还未完全吃透
pub fn is_match(s: String, p: String) -> bool {
    // 思路： 使用有穷状态自动机处理

    // 1. 生成有穷状态机
    let machine = create_NFA(p);

    // 当前状态
    let chs = s.chars().map(|c| c).collect::<Vec<char>>();

    match_by_nfa(&chs, &machine, 0, 0)
}

pub fn match_by_nfa(
    chs: &Vec<char>,
    machine: &HashMap<usize, state_machine_node>,
    index: usize,
    curr: usize,
) -> bool {
    let mut result = false;

    let node = machine.get(&curr).unwrap();

    // 执行空边
    if node.f.contains_key(&None) {
        result = match_by_nfa(chs, machine, index, *node.f.get(&None).unwrap());
    }

    if result {
        return true;
    }

    // 已经遍历完字符
    if index == chs.len() {
        return curr == machine.len() - 1;
    }

    let c = chs[index];

    // if node.f.contains_key(&None) {
    //     result = match_by_nfa(chs, machine, index, *node.f.get(&None).unwrap());
    // }

    if !result && node.f.contains_key(&Some(c)) {
        result = match_by_nfa(chs, machine, index + 1, *node.f.get(&Some(c)).unwrap());
    }

    if !result && node.f.contains_key(&Some('.')) {
        result = match_by_nfa(chs, machine, index + 1, *node.f.get(&Some('.')).unwrap());
    }

    result
}

// 题目21,合并两个有序链表  .https://leetcode-cn.com/problems/merge-two-sorted-lists/
pub fn merge_two_lists(
    list1: Option<Box<ListNode>>,
    list2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    match (list1, list2) {
        (Some(a), None) => Some(a),
        (None, Some(b)) => Some(b),
        (Some(a), Some(b)) => {
            if a.val < b.val {
                Some(Box::new(ListNode {
                    val: a.val,
                    next: merge_two_lists(a.next, Some(b)),
                }))
            } else {
                Some(Box::new(ListNode {
                    val: b.val,
                    next: merge_two_lists(Some(a), b.next),
                }))
            }
        }
        _ => Option::None,
    }
}


//  todo:  # 题目691， https://leetcode.cn/problems/stickers-to-spell-word/
pub fn min_stickers(stickers: Vec<String>, target: String) -> i32 {
    // 思路： 先解析出target中所有字符的元素和个数的集合S(c,i) ,c为元素字符，i为该元素的次数
    // 再解析出每个sticker中出现的元素和个数 V(c,i);
    // 对每个sticker按照出现的集中S中c次数降序排列，
    // 不考虑折枝，应该存在比折枝效率更高的方案？

    let mut map= HashMap::new();

    // 解析target
    target.chars().for_each( | c | {
        let  res: Option<&mut sticker_parse_char_record > = map.get_mut(&c);
        if  res.is_some(){
            let mut record = res.unwrap();
            record.count += 1;
        }else{
            let record = sticker_parse_char_record{c,count:1,index:None};
            map.insert(c.clone(),record);
        }
    });

    // 解析stickers
    let mut index = 0;
    for sticker in stickers {
        sticker.chars().for_each(|c| {
            if map.contains_key(&c) {
                let record_op = map.get_mut(&c);
                if record_op.is_some(){
                    let mut record= record_op.unwrap();
                    match record.index.as_mut() {
                        None => {
                            let mut v = Vec::new();
                            v.push(index.clone());
                            record.index = Some( v);
                        }

                        Some(v) => {
                            v.push(index.clone());
                        }
                    }
                }
            }
        });
        index +=1;
    };


    //
    let mut set = HashSet::new();
    let mut result = 0;
    map.values().for_each(|v|{
       if v.index.is_none(){
           result = -1 ;
       } else {
           for i in v.index.as_ref().unwrap() {
               println!("{}",i);
               set.insert(i);
           }
       }
    });


    match result {
        -1 => {-1}
        _=>{ set.len() as i32 }
    }


}

// 解析记录
#[derive(Debug,PartialEq,Hash)]
pub struct sticker_parse_char_record{
    // 字符
   pub c:char ,
    // 字符c在target中出现的次数
   pub count:usize,
    // 字符c在stickers中出现的索引位置集合
   pub index:Option<Vec<usize>>,
}





#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

// 栈节点
#[derive(Debug, Clone)]
pub struct StackNode<T> {
    val: T,
    next: Option<Box<StackNode<T>>>,
}

// 用链表实现一个栈
#[derive(Debug)]
pub struct Stack<T> {
    top: Option<Box<StackNode<T>>>,
    len: i32,
}

impl<T> Stack<T> {
    fn new() -> Stack<T> {
        Stack { top: None, len: 0 }
    }

    fn pop(&mut self) -> Option<T> {
        match self.top.take() {
            None => None,
            Some(node) => {
                self.len -= 1;
                self.top = node.next;
                Some(node.val)
            }
        }
    }

    fn push(&mut self, t: T) {
        let mut node = StackNode { val: t, next: None };
        let next = self.top.take();
        node.next = next;
        self.top = Some(Box::new(node));
        self.len += 1;
    }
}

// 获取数字的位数，例如 x=123,则应该返回3，x=10,则返回2 ,如果x不能为负数
pub fn get_num_len(x: i32) -> i32 {
    if 0 < x && x < 10 {
        return 1;
    }

    let mut y = 10;
    let mut len = 2;
    let mut z = x / y;
    while z > 10 {
        y *= y;
        len += 1;
        z = x / y;
    }

    len
}

// 获取单个罗马字符对应的数值
// 字符          数值
// I             1
// V             5
// X             10
// L             50
// C             100
// D             500
// M             1000
//
pub fn get_remo_value(c: char) -> i32 {
    match c {
        'I' => 1,
        'V' => 5,
        'X' => 10,
        'L' => 50,
        'C' => 100,
        'D' => 500,
        'M' => 1000,
        _ => panic!("不识别的字符:{}", c),
    }
}

// 测试-----------------
#[test]
fn test_min_stickers(){
    // let v = vec!["with".to_string(),"example".to_string(),"science".to_string()];
    // let target = "thehat".to_string();
    //
    // let result = min_stickers(v,target);
    // assert_eq!(3,result);




    let v= vec! ["these".to_string(),"guess".to_string(),"about".to_string(),"garden".to_string(),"him".to_string()];
    let target = "atomher".to_string();
    let result = min_stickers(v,target);
    assert_eq!(3,result);

}







#[test]
fn test_two_sum() {
    let mut v = Vec::new();
    v.push(1);
    v.push(3);
    v.push(5);

    let target = 6;

    let result = two_sum(&v, target);

    assert_eq!(v[result[0] as usize] + v[result[1] as usize], target);
}

#[test]
fn test_get_num_len() {
    let x = 2313;
    let len = get_num_len(x);
    assert_eq!(len, 4);
}

#[test]
fn test_is_palindrome() {
    let x = 12321;
    assert_eq!(true, is_palindrome(x));
    let x = 1121;
    assert_eq!(false, is_palindrome(x));
    let x = 10;
    assert_eq!(false, is_palindrome(x));
    let x = 1;
    assert_eq!(true, is_palindrome(x));
    let x = 0;
    assert_eq!(true, is_palindrome(x));
    let x = -10;
    assert_eq!(false, is_palindrome(x));
}

#[test]
fn test_roman_to_int() {
    let s = "III".to_string();
    assert_eq!(3, roman_to_int(s));
    let s = "IV".to_string();
    assert_eq!(4, roman_to_int(s));
    let s = "IX".to_string();
    assert_eq!(9, roman_to_int(s));
    let s = "LVIII".to_string();
    assert_eq!(58, roman_to_int(s));
    let s = "MCMXCIV".to_string();
    assert_eq!(1994, roman_to_int(s));
}

#[test]
fn test_longest_common_prefix() {
    let strs = vec![
        "flower".to_string(),
        "flow".to_string(),
        "flight".to_string(),
    ];
    assert_eq!("fl", longest_common_prefix(strs));

    let strs = vec!["dog".to_string(), "racecar".to_string(), "car".to_string()];
    assert_eq!("", longest_common_prefix(strs));
}

#[test]
fn test_option() {
    let o1 = Option::Some(2);
    let o2 = Option::Some(2);

    let pass = (o1 == o2);
    assert_eq!(true, pass);
}

#[test]
fn test_is_valid() {
    let s = String::from("()");
    assert_eq!(is_valid(s), true);
    let s = String::from("()[]{}");
    assert_eq!(is_valid(s), true);
    let s = String::from("(]");
    assert_eq!(is_valid(s), false);
    let s = String::from("([)]");
    assert_eq!(is_valid(s), false);
    let s = String::from("{[]}");
    assert_eq!(is_valid(s), true);
}

#[test]
fn test_length_of_longest_substring() {
    let s = "abcabcbb".to_string();
    assert_eq!(3, length_of_longest_substring(s));
    let s = "bbbb".to_string();
    assert_eq!(1, length_of_longest_substring(s));
    let s = "pwwkew".to_string();
    assert_eq!(3, length_of_longest_substring(s));
}

#[test]
fn test_number_of_lines() {
    let s = "abcdefghijklmnopqrstuvwxyz".to_string();
    let widths = vec![
        10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
        10, 10, 10,
    ];
    let result = number_of_lines(widths, s);
    assert_eq!(2, result.len());
    assert_eq!(3, result[0]);
    assert_eq!(60, result[1]);

    let s = "bbbcccdddaaa".to_string();
    let widths = vec![
        4, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
        10, 10, 10,
    ];
    let result = number_of_lines(widths, s);
    assert_eq!(2, result.len());
    assert_eq!(2, result[0]);
    assert_eq!(4, result[1]);

    let s = "mqblbtpvicqhbrejb".to_string();
    let widths = vec![
        3, 4, 10, 4, 8, 7, 3, 3, 4, 9, 8, 2, 9, 6, 2, 8, 4, 9, 9, 10, 2, 4, 9, 10, 8, 2,
    ];
    let result = number_of_lines(widths, s);
    assert_eq!(2, result.len());
    assert_eq!(1, result[0]);
    assert_eq!(100, result[1]);
}

#[test]
fn test_find_median_sorted_arrays() {
    let v1 = vec![1, 3];
    let v2 = vec![2];
    assert_eq!(2 as f64, find_median_sorted_arrays(v1, v2));

    let v1 = vec![1, 2];
    let v2 = vec![3, 4];
    assert_eq!(2.5 as f64, find_median_sorted_arrays(v1, v2));

    let v1 = vec![2, 2, 4, 4];
    let v2 = vec![2, 2, 4, 4];
    assert_eq!(3 as f64, find_median_sorted_arrays(v1, v2));

    let v1 = vec![0, 0, 0, 0, 0];
    let v2 = vec![-1, 0, 0, 0, 0, 0, 1];
    assert_eq!(0 as f64, find_median_sorted_arrays(v1, v2));

    let v1 = vec![1, 2];
    let v2 = vec![-1, 3];
    assert_eq!(1.5 as f64, find_median_sorted_arrays(v1, v2));
}

#[test]
fn test_convert() {
    let s = "PAYPALISHIRING".to_string();
    assert_eq!("PAHNAPLSIIGYIR", convert(s, 3));
    let s = "PAYPALISHIRING".to_string();
    assert_eq!("PINALSIGYAHRPI", convert(s, 4));
    let s = "A".to_string();
    assert_eq!("A", convert(s, 1));
    let s = "AB".to_string();
    assert_eq!("AB", convert(s, 1));
    let s = "ABCDE".to_string();
    assert_eq!("ABCED", convert(s, 4));
}

#[test]
fn test_reverse() {
    let x = 12345;
    assert_eq!(54321, reverse(x));

    let x = -100;
    assert_eq!(-1, reverse(x));

    let x = 2147483647;
    assert_eq!(0, reverse(x));
}

#[test]
fn test_myatoi() {
    let s = " 1234".to_string();
    assert_eq!(1234, my_atoi(s));

    let s = " +1234 ".to_string();
    assert_eq!(1234, my_atoi(s));

    let s = " -1234".to_string();
    assert_eq!(-1234, my_atoi(s));

    let s = " -acas 123".to_string();
    assert_eq!(0, my_atoi(s));

    let s = " +acas 123".to_string();
    assert_eq!(0, my_atoi(s));

    let s = " -23412 haha".to_string();
    assert_eq!(-23412, my_atoi(s));

    let s = " 214748364712323".to_string();
    assert_eq!(i32::MAX, my_atoi(s));

    let s = " -2147483648123asd".to_string();
    assert_eq!(i32::MIN, my_atoi(s));

    let s = "2147483648".to_string();
    assert_eq!(i32::MAX, my_atoi(s));
}

#[test]
fn test_is_match() {
    let s = "aa".to_string();
    let p = "a".to_string();
    assert_eq!(false, is_match(s, p));

    let s = "aa".to_string();
    let p = "a.".to_string();
    assert_eq!(true, is_match(s, p));

    let s = "aa".to_string();
    let p = ".*".to_string();
    assert_eq!(true, is_match(s, p));

    let s = "aa".to_string();
    let p = "a*".to_string();
    assert_eq!(true, is_match(s, p));

    let s = "abcdef".to_string();
    let p = "abc*".to_string();
    assert_eq!(false, is_match(s, p));

    let s = "abcdef".to_string();
    let p = "abc*def".to_string();
    assert_eq!(true, is_match(s, p));

    let s = "abcdef".to_string();
    let p = "abc*d.f".to_string();
    assert_eq!(true, is_match(s, p));

    let s = "aab".to_string();
    let p = "c*a*b".to_string();
    assert_eq!(true, is_match(s, p));

    let s = "ab".to_string();
    let p = ".*c".to_string();
    assert_eq!(false, is_match(s, p));

    let s = "aaa".to_string();
    let p = "a*a".to_string();
    assert_eq!(true, is_match(s, p));

    let s = "a".to_string();
    let p = "ab*".to_string();
    assert_eq!(true, is_match(s, p));

    let s = "bb".to_string();
    let p = "b*b".to_string();
    assert_eq!(true, is_match(s, p));
}

#[test]
fn test_merge_two_lists() {
    let node1_4 = ListNode { val: 4, next: None };
    let node1_2 = ListNode {
        val: 2,
        next: Some(Box::new(node1_4)),
    };
    let node1_1 = ListNode {
        val: 1,
        next: Some(Box::new(node1_2)),
    };

    let node2_4 = ListNode { val: 4, next: None };
    let node2_3 = ListNode {
        val: 3,
        next: Some(Box::new(node2_4)),
    };
    let node2_1 = ListNode {
        val: 1,
        next: Some(Box::new(node2_3)),
    };

    let mut result = merge_two_lists(Some(Box::new(node1_1)), Some(Box::new(node2_1)));

    loop {
        match result {
            Some(v) => {
                println!("{}", v.val);
                result = v.next
            }
            None => {
                break;
            }
        }
    }
}
